1. Field of the Invention
This invention relates generally to electronic digital computing and, more particularly, to a processing technique for executing queries in presence of type hierarchies using a logic-oriented language such as PROLOG, i.e., programs written in a programming language referred to in the art as PROLOG (PROgramming in LOGic).
2. Description of the Prior Art
A PROLOG program is written as a sequence of clauses. For example, a clause is written as follows to describe that Mary likes vegetables: EQU Likes(Mary,X).rarw.Vegetables(X). (1)
In a clause, .rarw.(or :--) is a logic symbol and the expressions on both sides of a logic symbol are called predicates. The words exemplified by "likes" and "vegetables" are referred to herein as predicate names. The word "Mary" and letter "X" are called arguments. A letter argument, e.g. "X", is a variable argument, and a word argument such as "Mary", is a constant argument.
Each predicate defines a relationship and includes a predicate name and a sequence of one or more arguments. The lefthand side of the logic symbol is called a head and the righthand side a body. A clause may have only the head. A clause having both a head and the body is called a rule, while a clause having only the head is called a fact (or an instance of predicate).
The predicate of the head and the predicate of the body are herein referred to as head predicate and body predicate, respectively. The head of a regular or a declaratory clause consists of only one head predicate, while the body of a regular or an interrogatory clause consists of one or more body predicates. When a body consists of N predicates, a comma is interposed between adjacent ones of the body predicates as follows: EQU Predicate(H).rarw.Predicate(1), . . . , Predicate(N). (2)
In clause (2), "Predicate(H)" represents a head predicate while "Predicate(1)" through "Predicate(N)" represent body predicates, N in number. The comma used between the body predicates is a logic symbol which means AND. Stated otherwise, the event represented by the head predicate is true only when all events represented by "Predicate(1)" through "Predicate(N)" hold. Let it be assumed that there is another clause in addition to clause (1) such that: EQU Vegetables(carrots). (3)
The sequence of clauses (1) and (3) represents the syllogistic deduction that Mary likes carrots.
As with most programming languages, it is possible to execute a PROLOG program on a conventional computer. Moreover, high-grade machinery is known in the art which is capable of processing various programming languages such as PROLOG. Also, dedicated PROLOG program processors are known, e.g., reference U.S. Pat. No. 4,546,432, by Umemura et al., entitled "PROLOG processing system."
Often, a class/subclass hierarchy (also referred to herein as a type hierarchy) is defined by a program to be processed. In such a hierarchy, there are typically one or more common nodes within the lattice. However, by definition, there are necessarily a smaller number of classes (types) in a particular program than there are objects (instances) in the search space. In PROLOG, a program representable as a type lattice is said to contain both type predicates and predicate instances. A type predicate comprises a predicate representative of a class of defined constants, while a predicate instance is a predicate with all arguments bound to constants (i.e., a fact).
Conventional PROLOG program processing utilizes certain predicate selection and clause selection strategies which almost always result in searching at the predicate instance level when query processing. However, in the presence of type hierarchies, searching type predicates before searching all predicate instances can result in enormous savings of query processing time. The present invention is directed to certain novel techniques for implementing such a concept.
Of the known prior art references, only the technique described by Kaci et al. in an article entitled "Logic and Inheritance," Proceedings of ACM SIGPLAN-SIGACT Conference on Principles of Programming Languages, discusses type lattice processing in a logic programming language. The approach described therein incorporates a processing of a type hierarchy during the unification (herein called matching) process. However, there is no mention of insuring that type predicates are processed before instance level searching occurs. Thus, the present invention is believed to offer a superior approach in terms of reducing search space.